1030E - Vasya and Good Sequences - CodeForces Solution

#include<bits/stdc++.h>
#define maxl 300010
 
using namespace std;
 
int n;
long long ans;
long long a[maxl],b[maxl],sum[maxl];
int f[maxl][2];
 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]),b[i]=__builtin_popcountll(a[i]);
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+b[i];
		if(sum[i]&1)
			f[i][1]=f[i-1][1]+1,f[i][0]=f[i-1][0];
		else
			f[i][0]=f[i-1][0]+1,f[i][1]=f[i-1][1];
	}
	ans=0;
	long long mx,tmp;
	for(int i=1;i<=n;i++)
	{
		mx=0;
		for(int j=i;j<=i+63 && j<=n;j++)
		{
			mx=b[j]>mx?b[j]:mx;
			if((sum[j]-sum[i-1])%2==0 && sum[j]-sum[i-1]>=mx*2)
				ans++;
		}
		if(i+63<n)
		{
			if(sum[i-1]&1)
				ans+=f[n][1]-f[i+63][1];
			else
				ans+=f[n][0]-f[i+63][0];
		}
	}
	printf("%lld\n",ans);
}